Prostokąt arytmetyczny

Limit pamięci: 128 MB

Na każdym polu kartki w kratkę, składającej się z kwadratów jednostkowych, zapisano jedną liczbę całkowitą. W tym zadaniu interesują nas prostokąty arytmetyczne położone na tej kartce, czyli takie prostokąty złożone z kwadratów jednostkowych, że liczby w każdym wierszu i w każdej kolumnie tworzą ciągi arytmetyczne. Przypomnijmy, że ciąg arytmetyczny to ciąg liczbowy, w którym każde dwa kolejne wyrazy różnią się o tę samą liczbę.

Na danej kartce w kratkę poszukujemy największego prostokąta arytmetycznego, tj. obejmującego najwięcej kwadratów jednostkowych. Przykładowo, największy prostokąt arytmetyczny na poniższej kartce składa się z dziewięciu kwadratów jednostkowych:

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę zestawów testowych opisanych w dalszej części wejścia. Opis każdego zestawu rozpoczyna się od wiersza z dwiema liczbami całkowitymi i (). W każdym z kolejnych wierszy znajduje się liczb całkowitych z zakresu od do . Są to liczby wpisane w poszczególne kwadraty jednostkowe kartki w kratkę. Rozmiar każdego pliku wejściowego będzie nie większy niż 20 MB.

Wyjście

Należy wypisać wierszy z odpowiedziami dla kolejnych zestawów testowych. Odpowiedzią dla jednego zestawu jest jedna liczba całkowita równa liczbie kwadratów jednostkowych zawartych w największym prostokącie arytmetycznym na kartce opisanej w danym zestawie.

Przykład

Dla danych wejściowych:

2
4 4
5 3 5 7
2 4 4 4
3 5 3 1
6 3 2 4
2 3
0 1 2
1 2 3

poprawną odpowiedzią jest:

9
6

Autor zadania: Jakub Radoszewski.